package middle;

import util.PrintUtils;

public class Solution_375 {

    public static void main(String[] args) {
        Solution_375 model = new Solution_375();
//        System.out.println(model.getMoneyAmount(1));
//        System.out.println(model.getMoneyAmount(2));
//        System.out.println(model.getMoneyAmount(10));
        for (int i = 1; i <= 20; i++) {
            System.out.println(model.getMoneyAmount(i));
        }
    }

    public int getMoneyAmount(int n) {
        int[][] array = new int[n+1][n+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n - i + 1; j++) {
                int min = Integer.MAX_VALUE;
                if (i == 1) {
                    min = 0;
                } else if (i == 2) {
                    min = j;
                } else {
                    for (int k = j + 1; k < j + i - 1; k++) {
                        int left = array[j][k - 1];
                        int right = array[k + 1][j + i - 1];
                        int max_k = Math.max(left, right) + k;
                        min = Math.min(max_k, min);
                    }
                }
                array[j][j + i - 1] = min;
            }
        }
        return array[1][n];
//        if (n == 1) {
//            return 0;
//        } else if (n == 2) {
//            return 1;
//        }
//        int[] array = new int[n + 1];
//        array[0] = 0;
//        array[1] = 0;
//        array[2] = 1;
//        for (int i = 3; i <= n; i++) {
//            array[i] = i - 3 + (i > 3 ? Math.max(i - 1, array[i - 4]) : i-1);
//        }
//        PrintUtils.arrayInt(array);
//        return array[n];

//        for (int i = 2; i <= n; i++) {
//            int min = Integer.MAX_VALUE, count = 0, split = 0, flag = 0;
//            for (int j = 1; j <= i; j++) {
//                int left = array[j - 1][1];
//                int right = array[i - j][1] + j * array[i - j][0];
//                int temp, temp_count;
//                if (left >= right) {
//                    temp = left + j;
//                    temp_count = array[j - 1][0] + 1;
//                } else {
//                    temp = right + j;
//                    temp_count =  array[i - j][0] + 1;
//                }
//                if (temp < min) {
//                    min = temp;
//                    count = temp_count;
//                    split = j;
//                    if (left >= right) {
//                        flag = 0;
//                    } else {
//                        flag = 1;
//                    }
//                } else if (temp == min) {
//                    count = Math.min(count, temp_count);
//                    if (temp_count < count) {
//                        split = j;
//                    }
//                }
//            }
//            array[i] = new int[]{count, min, split, flag};
//        }
//        PrintUtils.arrayInt(array);
//        return array[n][1];
    }
}
